#include <stdio.h>
#include <stdlib.h>  // 用于 malloc/realloc/free、exit
#include <stdbool.h> // 用于 bool 类型

/**
 * 扩展欧几里得算法：计算 ax + by = gcd(a,b)
 * @param a: 方程系数1
 * @param b: 方程系数2
 * @param x: 输出参数，x的解
 * @param y: 输出参数，y的解
 * @param g: 输出参数，gcd(a,b)
 * @return: 成功返回0，失败返回-1（内存分配失败）
 */
int extend_euclid(int a, int b, int *x, int *y, int *g) {
    // 确保 a >= b（与Python代码逻辑一致）
    if (a < b) {
        int ret = extend_euclid(b, a, y, x, g); // 交换x和y的指针
        return ret;
    }

    int *coefficients = NULL; // 存储 a//b 的系数列表
    int coeff_len = 0;        // 系数列表长度
    int coeff_cap = 4;        // 系数列表初始容量（动态扩容）

    // 初始化系数数组（动态分配，避免栈溢出）
    coefficients = (int *)malloc(coeff_cap * sizeof(int));
    if (coefficients == NULL) {
        fprintf(stderr, "错误：内存分配失败！\n");
        return -1;
    }

    // 循环计算系数 a//b，直到 b=0
    while (b != 0) {
        // 扩容逻辑（容量不足时翻倍）
        if (coeff_len >= coeff_cap) {
            coeff_cap *= 2;
            int *temp = (int *)realloc(coefficients, coeff_cap * sizeof(int));
            if (temp == NULL) {
                fprintf(stderr, "错误：内存分配失败！\n");
                free(coefficients);
                return -1;
            }
            coefficients = temp;
        }
        coefficients[coeff_len++] = a / b;
        int temp = b;
        b = a % b;
        a = temp;
    }

    // 初始化回代的x和y（对应Python的 x=1, y=0）
    *x = 1;
    *y = 0;
    *g = a; // 最终a即为gcd(a,b)

    // 系数列表逆序，循环回代（x, y = y, x - y*i）
    for (int i = coeff_len - 1; i >= 0; i--) {
        int new_x = *y;
        int new_y = *x - (*y) * coefficients[i];
        *x = new_x;
        *y = new_y;
    }

    // 释放动态内存
    free(coefficients);
    return 0;
}

/**
 * 丢番图方程求解：ax + by = c
 * @param a: 方程系数1
 * @param b: 方程系数2
 * @param c: 常数项
 * @param x0: 输出参数，x的特解
 * @param y0: 输出参数，y的特解
 * @param xk: 输出参数，x的通解系数（x = x0 + xk*t）
 * @param yk: 输出参数，y的通解系数（y = y0 + yk*t）
 * @return: 成功返回0，无解返回-1，内存错误返回-2
 */
int diophantine(int a, int b, int c, int *x0, int *y0, int *xk, int *yk) {
    int x_g, y_g, g;
    int ret = extend_euclid(a, b, &x_g, &y_g, &g);
    if (ret != 0) {
        return -2; // 内存分配失败
    }

    // 检查是否有解：c必须是gcd(a,b)的倍数
    if (c % g != 0) {
        fprintf(stderr, "错误：方程无解（%d 不是 gcd(%d,%d)=%d 的倍数）\n", c, a, b, g);
        return -1;
    }

    // 计算特解和通解系数（与Python逻辑一致）
    int k = c / g;
    *x0 = x_g * k;
    *y0 = y_g * k;
    *xk = b / g;
    *yk = -a / g;

    return 0;
}

int main() {
    // 测试用例：对应Python的 diophantine(6, 9, 27)
    int a = 6, b = 9, c = 27;
    int x0, y0, xk, yk;

    int ret = diophantine(a, b, c, &x0, &y0, &xk, &yk);
    if (ret == 0) {
        // 格式化输出（与Python测试结果格式一致，处理正负号）
        printf("solution is x = %d%s%d t, y = %d%s%d t\n",
               x0,
               xk > 0 ? " + " : " - ", // xk正显示"+"，负显示"-"
               xk > 0 ? xk : -xk,     // 负号单独处理，系数显示绝对值
               y0,
               yk > 0 ? " + " : " - ",
               yk > 0 ? yk : -yk);
    } else if (ret == -1) {
        return 1; // 无解，退出码1
    } else {
        return 2; // 内存错误，退出码2
    }

    return 0;
}